This invention relates to filters and, more particularly, to determining the median of a plurality of values.
A standard prior known approach in finding a median of N values is to fully sort the sequence of N values by arranging the N values in the sequence in either ascending or descending order, e.g., 4, 10, 20, . . . or . . . , 20, 10, 4, respectively, and then picking the middle value of the sorted sequence of N values. The optimal number of comparisons needed to sort N values is in the order of K*N*log(N), where K is some constant independent of N. This process of finding a median is not optimal, because the sorting is more than what is needed to locate the median. Sorting arranges all values in an ascending or a descending order. It produces the location of every value in the sequence, not only the median. In locating a median, only the median itself is of interest, it is not necessary to know the order of other values in the sequence. Therefore, using a full sorting process to locate the median is not optimal, and it requires making significantly more comparisons than are actually necessary.
The problems and limitations of prior spatial median filters is overcome in determining a median of a plurality of values, in accordance with the invention, by dividing the plurality of values into a plurality of groups of values. The values in each of the groups are sorted to determine its median. Then, the medians of the plurality of groups are fully sorted. Certain sorted values are eliminated from prescribed ones of the groups in accordance with prescribed criteria based on the number of values in the group and the median value of the group values. The remaining values are sorted to determine the median of the plurality of values.
A technical advantage of the invention is that fewer comparisons are required to determine the median of a plurality of values than in prior known arrangements. Consequently, this results in a significantly simpler implementation of a spatial median filter including an embodiment of the invention.
Another technical advantage of the invention is that in the process of determining the median values that are less than or equal and values that are greater than or equal to the median are also identified without any additional processing.